Proving Darwin by Gregory Chaitin

Author:Gregory Chaitin [Chaitin, Gregory]
Language: eng
Format: epub
ISBN: 978-0-307-90746-2
Publisher: Knopf Doubleday Publishing Group
Published: 2012-05-07T16:00:00+00:00

There is a beautiful essay on the web about this by the quantum computer complexity theorist Scott Aaronson, “Who Can Name the Biggest Number?,” which I highly recommend and which explains what a fundamental problem it is.

So that’s my fitness measure. Each of my software organisms calculates a single number, a single positive integer, and the bigger the number, the fitter the organism. The current organism A has a particular fitness N, and then we try a random mutation, according to the probability measure that I already explained, and if the resulting organism B calculates a bigger number, then it replaces A. Otherwise we try mutating A again.

Note that again we are implicitly making use of an oracle, because randomly mutating A will often produce a B that never halts and never calculates anything, so that we cannot determine if B is fitter than A—if B produces a number bigger than A does—by merely running B. We need to skip mutations that produce an invalid program B, as well as mutations that never produce a mutated organism B.

And to measure evolutionary progress, to measure the amount of biological creativity that is taking place, the rate of biological creativity, we use the so-called Busy Beaver function BB(N), which is defined to be the biggest positive integer that can be named with a ≤ N bit program. [This is a more refined version of the Busy Beaver function. The original Busy Beaver function BB(N) was the biggest integer calculated by a Turing machine with ≤ N states.]

BB(N) = largest positive integer named in ≤ N bits

BB(N) grows faster than any computable function of N, because BB(N) is essentially the same as the longest run-time of any ≤ N bit program that eventually halts. So if BB(N) were computable that would give us a way to solve the halting problem.

Okay, now let’s see what happens if we start with a trivial organism, for example the one that calculates the number 1, and we carry out this hill-climbing random walk. We apply mutations at random and look how fast the fitness will grow. In fact, to calibrate how fast cumulative random evolution will work, let’s see where it falls between

• brainless exhaustive search, in which the previous organism A is ignored and we try a new organism B at random (in other words, the mutations are produced by programs that are chosen at random as before, but that are not given any input),

• and the fastest possible evolution that we can get by picking a computable sequence of mutations in the best possible manner in order to make the fitness grow quickly, which I call “intelligent design.”

[You cannot use an oracle to jump directly to BB(N), BB(N+1), etc., because we are only allowing a highly restricted use of oracles, in determining whether A B is fitter than A. Furthermore, to eliminate mutations that don’t produce a B from A.]

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.